package Test;

import java.util.Arrays;

public class DemoTest {
    /*
    *给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

* 输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
     * */


    /*
  解题思路：使用三次逆转法，让数组旋转k次
    1. 整体逆置
    2. 逆转子数组[0, k - 1]
    3. 逆转子数组[k, size - 1]
*/
    class Solution {
        void rotate(int[] nums, int left, int right){
            while(left < right){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            rotate(nums, 0, nums.length-1);
            rotate(nums, 0, k-1);
            rotate(nums, k, nums.length-1);
        }

    }

    public void rotate(int[] nums, int k) {
        k%=nums.length;
        int front=0;
        int end=nums.length;
        for(int i=0;i<k;i++){
            front=nums[end-1];
            for(int j=end-1;j>0;--j){
                nums[j]=nums[j-1];

            }
            nums[0]=front;

        }
        for (int x:nums
             ) {
            System.out.println(x);

        }


    }

    public static void main(String[] args) {

        int[] i=new int[]{1,2,3,4,5,6,7};
        int k=3;
     DemoTest.Solution solution=new DemoTest().new Solution();
     solution.rotate(i,k);


    }
    public static void main2(String[] args) {
        DemoTest demoTest=new DemoTest();
        int[] i=new int[]{1,2,3,4,5,6,7};
        demoTest.rotate(i,3);

    }
    /*
    * 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
    * 示例 1：

    输入：[3,0,1]
    输出：2

     * 示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8
*
*
*
* */
     /*
    解题思路：
    直接将数组中所有元素之和sum，然后求出1~N的前N项和-sum即可
    时间复杂度O(N)，空间复杂度:O(1)
    缺陷：如果数组中元素比较多，相加完成之后容易溢出
     */
    public int missingNumber0(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; ++i){
            sum += nums[i];
        }


        return ((1+nums.length)*nums.length)/2 - sum;
    }

    /*
        解题思路：
          采用异或的方式解决，因为两个相同的数字异或的结果是0
          因此：将0~N之间的数字，与数组中的每个数字异或，
                最终的结果就是丢失的数字
     */
    public int missingNumber2(int[] nums) {
        int data = 0;
        for(int i = 0; i < nums.length; ++i){
            data ^= nums[i];
            data ^= i;
        }
        data ^= nums.length;
        return data;
    }

    /*
        解题思路：
        将1~N之间的数组相加，然后减去nums数组中的每个数字
     */
    public int missingNumber1(int[] nums) {
        int data = nums.length;
        for(int i = 0; i < nums.length; ++i){
            data = data - nums[i] + i;
        }
        return data;
    }

    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
            if(!(nums[i]==i)){

                return i;
            }

        }
        return nums.length;

    }
    public static void main1(String[] args) {

        int[] array=new int[]{0};

        System.out.println(DemoTest.missingNumber(array));
    }

}
